#ifndef __HYPO_LIST
#define __HYPO_LIST

#include "baseclas.h"
#include "feature.h"
#include "soundlab.h"
#include "segopt.h"
#include "tspecbas.h"
#include "tspecbas.hpp"

// dummy definition ImpObjectList<T> dummy; is needed somewhere
// in some member functions
// so that compiler istanziates at least one istance of
// ImpObjectList<T> and linker can find the member functions of the class

// *************************************************************
//
//					Class for HMM models
//
// *************************************************************


class RecogGaussian : public Gaussian
    { 
	public:
	    void operator=(const RecogGaussian & source);
	};

class RecogNodeSpecShape : public NodeSpecShape<RecogGaussian> {};
class RecogHmm : public Hmm<RecogNodeSpecShape> {};


// ***********************************************************
//															 *
//		      				 static structure				 *
//															 *
// ***********************************************************


typedef t_index natural;
typedef t_index t_ptr;

typedef t_ptr p_spec_table;
typedef	t_ptr p_acustic_state;
typedef	t_ptr p_grammar_state;

//second level
typedef t_ptr p_leaf;
typedef t_ptr p_kid;

typedef t_real t_lprob;

template <class T,class LABEL>
class Graph
	{
	public:

		class Branch
			{
			public:
				LABEL label;
				t_ptr p_node;

				void operator = (const Branch& act_branch)
					{
					label = act_branch.label;
					p_node = act_branch.p_node;
					return;
					};
			};

		class Node
			{
			public:
				T info;
				ImpObjectList<Branch> nexts;
			};

		ImpObjectList<Node> G;

		t_index Num_Successors(t_ptr p_node) const
			{
			return(G[p_node].nexts.Dim());
			}

		Node &  operator [] ( const t_index index )
			{
			return(G[index]);
			}

		const Node &  operator [] ( const t_index index ) const
			{
			return(G[index]);
			}

	};


class StaticNode
	{
	public:
		t_lprob obs;
		t_ptr link;
	};

typedef  Graph<StaticNode, t_lprob> LinkedGraph;

// DEFINITION OF A MULTILEVEL GRAMMAR RECOGNITION STRUCTURE.         //
// pure virtual functions makes the class independent from           //
// the particulart kind of observation and recognition unit          //

//   *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *   //
//                                                                   //
//                        GENERIC STATIC HMM                         //
//                                                                   //
//   *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *   //


class GenericStaticHmm
	{
	public:
		// obs_statf: file with observation statistical description
		ifstream recog_dataf;
		// conversion table from the node labels of the top level graph
		// ( = numerical pointers ) and recognition units
		ImpObjectList<String> last_level_symbols;
		//pay attention
		//grammar[l] select the linked graph at level l
		//grammar[l] [j]   select the jth node in the
		//			linked graph at level l
		// base_node.state[l] gives the pointer to node of
		// 		          the graphic at level l
		// 		      if base_node is an HypoNode

		ImpObjectList<LinkedGraph> grammar;

		// single hypotesis unit
		class HypoNode
			{	
			friend class GenericStaticHmm;
			protected:
				// accumulated path score
				t_lprob log_prob_acc;

				// beginning of a new recognition unit necessary
				// in order to disciminate recognition unit node self-cycle
				//hypotesis coordinate
			public:
				int new_unit;
				ImpSimpleTypeList<t_ptr> state;

				int operator!=(const HypoNode& node) const;
				int operator==(const HypoNode& node) const;
				int Is_Worse_Then(const HypoNode& node) const;

				t_real Add_To_LProb_Acc(const t_lprob lprob);
				t_real Log_Prob_Acc()
					{
					return log_prob_acc;
					}
			};

		class HypoList: public ImpObjectList<HypoNode>{};

		// Observed_Hypo_List_From_Silence: in ris_list list of successors of
		// silence updated with observation probability
		void Observed_Hypo_List_From_Silence(HypoList & ris_list,
					 const HypoNode & silence);

		void Observed_Hypo_List_From_This_Node(HypoList & ris_list,
							const HypoNode & act_node);

		// Append_Successors_To: given a node (base node) valid till level
		// "level_to_change-1"returns a list of nodes and calculates
		// the log_prob_acc i.e the log probability accumulated
		// an empty list returned means that there are no more observations
		void Append_Successors_To(HypoList& list, const HypoNode & base_node,
						const t_index l);

		// Append_Lowest_Level_Hypos_To:
		void Append_Lowest_Level_Hypos_To(HypoList & list,
									HypoList& act_level_list, t_index l);

		// Set_To_Silence: sets first node of hypotesis tree
		void Set_To_Silence(HypoNode& act_node);

		// Get_Observation: gets sequentially observation units,
		// returns TRUE while input is not ended, FALSE on the end of the input
		virtual int Get_Observation(int& new_file, DbaseVoc& dbase)=0;

		// Obs_LProb: computes observation log-probabilities
		virtual t_lprob Obs_LProb(const t_ptr pnode_stat)const =0 ;

	};




// *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  //
//                                                                      //
//                           SPECTRALHMM                                //
//                                                                      //
//        (derived class for recognition from acoustic information)     //
// *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  //

class SpectralHmm: public GenericStaticHmm
	{
	public:
		FeatureExtraction features;
		VetInt phonemes_map;

		// sample shift between two following frames
		t_index frame_shift;
		t_index win_len;
    
		// spectral description of one 1-level states(nodes)
		RecogHmm spectral_model;
		VetDouble observation;

		// Initialise_Structures: opens trained phonemes models file and
		// initialises dbase voc and phonemes statistical representation
		// codebook
	
		void Initialise_Structures(const String& config_file, const SegmentOptions& options,
										const DbaseVoc& dbase);

		void Build_Grammar_Over_Phonemes(const VetULong& utter_label_list,
	                                                    int sil_opt, const DbaseVoc& dbase);

		void Set_Single_Phon_Graph(const MatrixOfDouble &trans_mat, LinkedGraph& act_graph,
							const t_index old_cb_dim, const t_index old_graph_dim);

		void Dump_Utterance_Segmentation_Ares(const GenericStaticHmm::HypoList& decoded_list,
											String& phn_fname, t_index sample_rate);
		void Dump_Utterance_Segmentation_Ares(const GenericStaticHmm::HypoList& decoded_list,
											const String& phn_fname, t_index sample_rate);

		void Dump_Utterance_Segmentation_Res(const GenericStaticHmm::HypoList& decoded_list,
											String& phn_fname);
		void Dump_Utterance_Segmentation_Res(const GenericStaticHmm::HypoList& decoded_list,
											const String& phn_fname);

		int Get_Observation(int& new_file, DbaseVoc& dbase);

		t_lprob LogAdd(t_lprob x, t_lprob y)const;

		t_lprob Obs_LProb(const t_ptr pcluster)const;

	};

// *************************************************************************
//									   *
//		            DYNAMIC STRUCTURE				   *
//									   *
// *************************************************************************


//we hypotize that one node can't generate twice tha same node


//FIRST LEVEL LINKED BUFFERED LIST WITH EMBEDDED FREE LIST

//linked sparse list con lista libera NUll pointer is zero index
//zero index poinnter non accessible
template <class T>
class SparseList
	{
		t_ptr free_list;
		t_ptr start_list;
		natural dim_free;
		natural chunk_size;

		class Node
			{
			friend SparseList<T>;
				T info;
				t_ptr link;
				t_index num_kids;
			public:

				static t_index Kids_Of_Free_Node()
					{
					return(t_index)(-1);
					}

				Node()
					{
					num_kids=this->Kids_Of_Free_Node();
					}
			}; // class Node

		ImpObjectList<Node> List;
	
	public:

		void Reset();
		//when freelist finishes chunk size elements allocated in free list
		SparseList(natural chunk_size=100);

		void Restart();

		//return ptr to node created
		t_ptr  Create(const T & info,t_ptr parent);

		//error message if referenced node
		void Destroy_Node(t_ptr node);

		//error message if referenced node
		//Destroy Branc nodes until referenced node
		void Destroy_Branch(t_ptr node);

		// retrieves list of info of connected nodes starting from node
		// assumes that T has an operator = that duplicates the classes
		void Backtrack_From(ImpObjectList<T> & sequence,t_ptr node);

		t_ptr Next(t_ptr node) const;

		T & operator[](const t_ptr node);
		const T & operator[](const t_ptr node)const;
	
		t_index Num_Node() const;

		int Has_No_Kids(t_ptr t_node) const;

	protected:
		void Allocate_Mem();

	};


//SECOND LEVEL
template<class T>
class WellTree
	{
	friend class HypoTree;

		SparseList<T> l_list;
		ImpSimpleTypeList<t_ptr> leaves_dir; //start of last level nodes
		ImpSimpleTypeList<t_ptr> kid_dir;    //start of new level (or end of tree)

	public:

		~WellTree();
		void Reset();

		//needed by Viterbi.num_attivi
		t_index Num_Elements() const;
		t_index Kids_Dim() const;
		t_index Leaves_Dim() const;

		void Exchange_Leaves_Indexes(const t_index i, const t_index j);
		void ReDim_Leaves_Dir_To(const t_index ix);

		//Check_Kid_Presence_And_Get_Num: checks for the presence of act_kid in kid_dir
		int Check_Kid_Presence_And_Get_Num(const T & act_kid, p_kid & num_kid);

		const T& Get_Leaf_Info(const p_leaf leaf)const;

		T& Get_Leaf_Info(const p_leaf leaf);

		const T& Get_Kid_Info(const p_kid kid)const;

		T& Get_Kid_Info(const p_kid kid);
	
		void Create_First_Leaf_Of_Tree(const  T& info);

		void Add_Kid_To_Leaf(const T & info,p_leaf leaf);

		void Prune_All_Dead_Leaf();

		void Prune_Blind_Branch_From_Leaf(p_leaf leaf);

		//Backtrack_from(a_node) returns a new list with every element
		//containing address of every nodes along path sequence
		void Backtrack_From(ImpObjectList<T> & sequence,p_leaf leaf);

		//start the next generation
		//transform kid_dir leaves_dir;
		void Next_Gen(); // leaves=kid

		void Subst_Old_Kid_Destroy_Old_Branch_Ins_New(p_kid old_kid,
					const  T & info,p_leaf new_father);

	};

// **********************************************************************
//                                                                     *
//                third level                                          *
//                                                                     *
// **********************************************************************

//we hypotize that one node can't generate twice tha same node

//class header

typedef t_index p_candidate;
typedef t_index p_active;

class HypoTree
	{
		WellTree<GenericStaticHmm::HypoNode> tree;
		//actives are actives-node at step K
		//candidates are actives-node at step K+1
		//p_active p_candidate are pointers to active and candidate respectively
		//t_index are unsigned long numbers

	public:

		t_index Candidates_Dim() const;
		t_index Actives_Dim() const;

		const GenericStaticHmm::HypoNode & Get_Candidate(p_candidate num);
		GenericStaticHmm::HypoNode & Get_Active(p_candidate num);
	
		void Prune_All_Dead_Active();

		// check if adds an already present node, if so select the best one
		int Check_Candidate_Presence_And_Get_Num(const GenericStaticHmm::HypoNode & info,
								p_candidate& num_candidate);

		int Check_Candidate_Presence_And_Get_Num(VetInt& candidate_map,
				 				p_candidate & num_candidate,
								const GenericStaticHmm::HypoNode & info);

		// the following function calls WellTree.read_node_info(const & t_node node);

		int Node_Is_Worse_Then_Candidate(const GenericStaticHmm::HypoNode& node,
								p_candidate & num_candidate);

		void Create_First_Active_Of_Tree(const GenericStaticHmm::HypoNode & node);

		void Add_Candidate_To_Active_Num(const GenericStaticHmm::HypoNode & node,
								p_active num_active);

		//following funcs call the same
		//prune_branch_from_node in WellTree class
		void Prune_Branch_From_Active(p_active num_active);

		void Subst_Old_Cand_Destroy_Old_Branch_Ins_New(p_candidate old_kid,
				const  GenericStaticHmm::HypoNode & info,p_active new_father);

		void Transform_Next_Generation_In_Actives();

		void UpDate_Actives_LProb_Acc(VetDouble& scores,const GenericStaticHmm& hmm);

		void Window_Search(VetDouble& scores, const t_index max_num_activate);

		void Exchange_Actives_Indexes(const t_index i, const t_index j);

		void ReDim_Tree(const t_index max_dim_tree, const t_index max_num_activate);

		void Reduce_Actives_To(const t_index ix);

		p_active Worse_Active();

		p_active Best_Active();

		//Backtrack_from active returns a new list sequence
		//with every element
		//containing nodes info of Viterbi best path sequence
		void Backtrack_From(GenericStaticHmm::HypoList & sequence, p_active active);

		int Viterbi(GenericStaticHmm::HypoList & sequence, t_index max_num_activate,
				t_index max_dim_tree, int& new_file, GenericStaticHmm & hmm, 
				DbaseVoc& dbase);

		void Beam_Search(VetDouble& scores, t_real& threshold,
												const t_real beam_coeff);
   
		void ReDim_Tree(const t_real threshold);	
   
		int Viterbi_Beam(GenericStaticHmm::HypoList & sequence, t_real beam_coeff,
				int& new_file, GenericStaticHmm & hmm, DbaseVoc& dbase);

	};
//=============================================================================


template<class T>
int SparseList<T>::Has_No_Kids(t_ptr node) const
	{
	//dummy definition so that compiler istanziates at least one istance of
	//ImpObjectList<T> and linker can find the member function of the class
	ImpObjectList<T> dummy;
	return((int)(List[node].num_kids==0));
	}

template<class T>
SparseList<T>::SparseList(natural chunk)
	{
	chunk_size=chunk;
	free_list=0;
	start_list=0;
	dim_free=0;
	//allocate the nihil=0 element this can't be used
	List.Destroy_And_ReDim(1);
	return;
	}

template<class T>
void SparseList<T>::Restart()
	{
	free_list=0;
	start_list=0;
	dim_free=0;
	//allocate the nihil=0 element this can't be used
	List.Destroy_And_ReDim(1);
	return;
	}

template<class T>
void SparseList<T>::Reset()
	{
	free_list=0;
	start_list=0;
	dim_free=0;
	return;
	}

template<class T>
void SparseList<T>::Allocate_Mem()
	{
	natural i;
	t_ptr temp=List.Dim();
	List.Save_And_ReDim(chunk_size+temp);
	for(i=temp;i<temp+chunk_size-1;i++)
		{
		List[i].link=i+1;
		}
	List[List.Dim()-1].link=free_list;
	free_list=temp;
	dim_free+=chunk_size;
	return;
	}

template<class T>
t_ptr SparseList<T>::Create(const T & info,t_ptr parent)
	{
	t_ptr temp;
	if (free_list==0)
		Allocate_Mem();
	//get one node from free list
	temp=free_list;
	free_list=List[temp].link;
	dim_free--;

	//verify that free_node is really free
	Assert(List[temp].num_kids==Node::Kids_Of_Free_Node());
	List[temp].link=parent;
	List[temp].num_kids=0;
	List[temp].info=info;
	List[parent].num_kids++;
	return temp;
	}

template<class T>
t_ptr SparseList<T>::Num_Node() const
	{
	return(List.Dim()-dim_free-1);
	}

template<class T>
t_ptr SparseList<T>::Next(t_ptr son) const
	{
	Assert(son>0);
	return List[son].link;
	}

template<class T>
void SparseList<T>::Destroy_Node(t_ptr node)
	{
	Assert(node>0);
	if(List[node].num_kids>0)
		merr<<"Attempt to Destroy referenced node";

	//decrease parent's num_kids
	List[Next(node)].num_kids--;
	//add to free list
	List[node].link=free_list;
	free_list=node;
	List[free_list].num_kids=Node::Kids_Of_Free_Node();
	dim_free++;
	return;
	}

template<class T>
void SparseList<T>::Backtrack_From(ImpObjectList<T> & sequence,
							t_ptr node)
	{
	t_index i=0;
	Assert(node>0);

	sequence.Reset();
	do	{
		sequence.Save_And_ReDim(i+1);
		sequence[i]=(*this)[node];
		i++;
		node=Next(node);
		}
	while ( node!=0);
	// eliminate phantom node
	// is the following instruction necessary in order to eliminate
	// silence and duplicated hypo?
	sequence.Save_And_ReDim(i-1);
	T temp;
	for(i=0;i<sequence.Dim()/2;i++)
		{
		temp=sequence[i];
		sequence[i]=sequence[sequence.Dim()-i-1];
		sequence[sequence.Dim()-i-1]=temp;
		}
	return;
	}


template<class T>
void SparseList<T>::Destroy_Branch(t_ptr node)
	{
	t_ptr temp;
	Assert(node>0);
	if(List[node].num_kids>0)
		merr<<"Attempt to destroy referenced node";
		
	do	{
		temp=Next(node);
		Destroy_Node(node);
		node=temp;
		} 
	while (List[node].num_kids==0 && node!=0);
	return;
	}

template<class T>
T & SparseList<T>::operator[](const t_ptr son)
	{
	Assert(son>0);
	Assert(List[son].num_kids != Node::Kids_Of_Free_Node());
	return List[son].info;
	}

template<class T>
const T & SparseList<T>::operator[](const t_ptr son)const
	{
	Assert(son>0);
	Assert(List[son].num_kids != Node::Kids_Of_Free_Node());
	return List[son].info;
	}

//SECOND LEVEL

template<class T>
WellTree<T>::~WellTree()
	{
	l_list.Reset();
	leaves_dir.Reset();
	kid_dir.Reset();
	}

template<class T>
void WellTree<T>::Reset()
	{
	leaves_dir.Reset();
	kid_dir.Reset();
	l_list.Restart() ;
	}

//needed by Viterbi.num_hypotesis
template<class T>
inline t_index WellTree<T>::Num_Elements() const
	{
	return (l_list.Num_Node());
	}

template<class T>
inline t_index WellTree<T>::Kids_Dim() const
    {
	return kid_dir.Dim();
	}

template<class T>
inline t_index WellTree<T>::Leaves_Dim() const
	{
	return leaves_dir.Dim();
	}

//const & T info read_leaf_info(p_leaf  leaf) const;
template<class T>
void WellTree<T>::ReDim_Leaves_Dir_To(const t_index ix)
	{
	leaves_dir.Save_And_ReDim(ix);
	return;
	}

template<class T>
inline void WellTree<T>::Exchange_Leaves_Indexes(const t_index i,
								const t_index j)
	{
	t_index aux;
	aux=leaves_dir[i];
	leaves_dir[i]=leaves_dir[j];
	leaves_dir[j]=aux;
	return;
	};

template<class T>
int WellTree<T>::Check_Kid_Presence_And_Get_Num(const T & act_kid,
						p_kid & kid_idx)
	{
	t_index i=0, kid_num;
	kid_num = kid_dir.Dim();
	if (kid_num==0)
		{
		return (int) false;
		}
	else{
		while(i<kid_num && act_kid != l_list[kid_dir[i]])
			i++;
				
		if(i==kid_num)
			return (int)false;
		else{
			kid_idx=i;
			return (int)true;
			}
		}
	}

template<class T>
inline const T& WellTree<T>::Get_Leaf_Info(const p_leaf leaf)const 
	{
	return (l_list[leaves_dir[leaf]]);
	}

template<class T>
inline T& WellTree<T>::Get_Leaf_Info(const p_leaf leaf) 
	{
	return (l_list[leaves_dir[leaf]]);
	}


template<class T>
inline const T& WellTree<T>::Get_Kid_Info(const p_kid kid)const
	{
	return (l_list[kid_dir[kid]]);
	}

template<class T>
inline T& WellTree<T>::Get_Kid_Info(const p_kid kid)
	{
	return (l_list[kid_dir[kid]]);
	}

template<class T>
inline void WellTree<T>::Create_First_Leaf_Of_Tree(const  T& info)
	{
	//if no elements in tree create leaf
	Assert(l_list.Num_Node()==0);
	leaves_dir.Destroy_And_ReDim(1);
	//0 pointer is NULL
	leaves_dir[0]=l_list.Create(info,0);
	return;
	}

template<class T>
inline void WellTree<T>::Add_Kid_To_Leaf(const  T& info, p_leaf leaf)
	{
	//if no elements in tree create leaf
	if(l_list.Num_Node()==0)
		{
		leaves_dir.Destroy_And_ReDim(1);
		//0 pointer is NULL
		leaves_dir[0]=l_list.Create(info,0);
		return;
		}

	//abort if tree not empty and no leaves
	Assert(l_list.Num_Node()>0 && leaves_dir.Dim()!=0);

	//abort if more than one well created
	Assert(l_list.Num_Node()>0 && leaves_dir[leaf]!=0);

	t_index kid_dim=kid_dir.Dim();
	kid_dir.Save_And_ReDim(kid_dim+1);

	kid_dir[kid_dim]=l_list.Create(info,leaves_dir[leaf]);
	return;
	}

template<class T>
void WellTree<T>::Prune_All_Dead_Leaf()
	{
	t_index i;
	// here its not necessary to update leaves_dir
	// since next_gen follows
	for(i=0;i<leaves_dir.Dim();i++)
		{
		if (l_list.Has_No_Kids(leaves_dir[i]) )
				Prune_Blind_Branch_From_Leaf(i);
		}
	return;
	}

template<class T>
inline void WellTree<T>::Prune_Blind_Branch_From_Leaf(p_leaf leaf)
	{
	Assert(leaves_dir.Dim()>=1);
	l_list.Destroy_Branch(leaves_dir[leaf]);
	return;
	}

//Backtrack_from(a_node) returns a new list with every element
//containing address of every nodes along path sequence
template<class T>
inline void WellTree<T>::Backtrack_From(ImpObjectList<T> & sequence,p_leaf leaf)
	{
	l_list.Backtrack_From(sequence,leaves_dir[leaf]);
	}

//start the next generation
//transform kid_dir leaves_dir;
template<class T>
inline void WellTree<T>::Next_Gen() // leaves=kid
	{
	leaves_dir=kid_dir;
	kid_dir.Reset();
	return;
	}

template<class T>
inline void WellTree<T>::Subst_Old_Kid_Destroy_Old_Branch_Ins_New(p_kid old_kid,
					const  T & info,p_leaf new_father)
	{
	l_list.Destroy_Node(kid_dir[old_kid]);
	kid_dir[old_kid]=l_list.Create(info,leaves_dir[new_father]);
	return;
	};
#endif
